#include <stdio.h>
#include <stdlib.h>

struct list {
  int num;
  struct list * prev;  // 对prev的访问，只有删除时用到，插入时用不到
  struct list * next;
};

struct list * init(void)
{
  struct list * head;

  head = (struct list *) malloc (sizeof(struct list));
  if (!head) {
    printf(" init malloc fail.\n");
    exit(-1);
  }

  return head;
}

struct list * create(struct list * head) 
{
  struct list * src, * new;
  int value;

  src = head;		// 指向头结头,头结点一直停在头结点,靠src指针下移.
  scanf("%d", & value);
  while (value != 0) {
    new = (struct list *) malloc (sizeof(struct list));
    src->next = new;    // 头结点后继指向新节点
    new->prev = src;    // 新结点前驱指向头结点
    new->num = value;
    src = new;          // 头结点指向新结点.即头移到下一个结点.
    scanf("%d", & value);
  }

  head->prev = src;     // 头结点前驱指向最后一个结点.
  src->next = head;     // 最后结点后驱指向头结点

  return head;
}

void display(struct list * head)
{
  struct list * src;

  printf("since head print:\n");
  src = head;
  src = src->next;		// head为头结点,没有存num值,所以要指向下一个
  do {
    printf(" %d ", src->num);
    src = src->next;
  } while (src != head); // 以头结点结束

  printf("\n");

  printf("since rear print:\n");
  src = head;
  src = src->prev;
  do {
    printf(" %d ", src->num);
    src = src->prev;
  } while (src != head);

  printf("\n");
}

struct list * find(struct list * head, int position)
{
  struct list * src;
  int pos = 0;

  src = head;
  while ((src->next != head) && (pos < position)) {
    src = src->next;
    pos++;
  }
  
  if (position == pos) 
    return src;
  else
    return NULL;
}

int location(struct list * head, int value)
{
  struct list * src;
  int pos = 0;
  
  src = head;
  while ((src->next != head) && (src->num != value)) {
    src = src->next;
    pos++;
  }

  if (src->num == value)
    return pos;
  else
    return 0;
}

struct list * insert(struct list * head, int position, int value)
{
  struct list * src, * des;

  src = find(head, position - 1);
  if (!src) {
    printf("position is not existence.\n");
    return NULL;
  }
  else {
    des = (struct list *) malloc (sizeof(struct list));
    des->num = value;
    des->prev = src;        // 新结点前驱指向前结点.
    des->next = src->next;  // 新结点后驱指向下一个结点.
    src->next->prev = des;  // 下一个结点的前驱指向新结点.
    src->next = des;        // 原先的src->next指向新结点.即新结点插入.
  }

  return head;
}

struct list * delete(struct list * head, int position)
{
  struct list * src;

  src = find(head, position);
  if ((src != NULL) && (src->next != NULL)) {
    src->prev->next = src->next;  // 要删除结点的前结点后驱指向要删除结点的下结点.即前结点向后指.
    src->next->prev = src->prev;  // 要删除结点的后结点前驱指向要删除结点的上结点.即后结点向前指.
    free(src);
  }
  else 
    return NULL;

  return head;
}


int length(struct list * head)
{
  struct list * src;
  int pos = 0;

  src = head;
  while (src->next != head) {
    src = src->next;
    pos++;
  }

  return pos;
}

int main()
{
  struct list * head, * src;
  int input, count;

  head = init();

  printf("input number, zero exit:\n");
  head = create(head);
  display(head);

  printf("input find position:\n");
  scanf("%d", & count);
  src = find(head, count);
  printf("The position %d of value is %d\n", count, src->num);

  printf("input find number:");
  scanf("%d", & input);
  count = location(head, input);
  printf("The value's  position is : %d\n", count);

  printf("input insert value and position:");
  scanf("%d %d", & count, & input);
  head = insert(head, count, input);
  display(head);

  printf("input delete position:");
  scanf("%d", & input);
  head = delete(head, input);
  display(head);

  count = length(head);
  printf("take head node of double list of length is : %d\n", count);
}
